package class_0826HashTable;

import java.util.HashMap;
import static java.lang.Math.random;
/**
 * 用哈希表模拟有序
 * 生成随机取数样本
 * @author 90774
 */
public class RandomPool {
    /**
     * map1 :下标-值
     * map2 : 值-下标
     * size : 计数器。
     * 改一改可以把哈希表当初有序表用了
     * @param <K>
     */
    public static class Pool<K>{
        HashMap<Integer,K> map1;
        HashMap<K,Integer> map2;
        public int size;
        public Pool(){
            map1 = new HashMap<Integer,K>();
            map2 = new HashMap<K,Integer>();
            size = 0;
        }
        public void insert(K key){
            if(!map2.containsKey(key)) {
                map1.put(size, key);
                map2.put(key, size);
                size++;
            }
        }
        public void delete(Integer index){
            if(!map1.containsKey(index)) {
                //根据 表1从取末尾数覆盖表1对应位置，原位置删除。
                int lastIndex = --this.size;
                K key = map1.get(lastIndex);
                map1.put(index, key);
                map1.remove(lastIndex);
                map2.remove(key);
                size--;
            }
        }
        public void delete(K key){
            Integer index = map2.get(key);
            delete(index);
        }
        public K getRandom(){
            if(size==0){
                return null;
            }
            else{
                //生成一个0~size-1的下标
                int randIndex = (int)random()%size;
                return map1.get(randIndex);
            }
        }
    }
}
